package com.hanlin.day04;

import com.hanlin.day01.DataSort;

/**
 * 算法入门：二分
 *
 * @Author: hl.yuan
 * @Date: 2021/5/31 16:54
 */
public class DataBranch {

    /**
     * 查找num这个数存不存在
     *
     * @param array 数组 ：保证有序
     * @param num   要查找的数
     * @return
     */
    public static boolean findArrayData(int[] array, int num) {
        // 最大值的下标
        int maxIndex = array.length - 1;
        // 二分的位置
        int branchIndex = 0;
        while (branchIndex <= maxIndex) {
            // 下标
            int index = (branchIndex + maxIndex) / 2;
            // 如果二分的位置，小于num，说明不合适
            if (array[index] < num) {
                // 左边的数据都小于，直接舍弃左边的，故下次二分的位置是index+1
                branchIndex = index + 1;
            } else if (array[index] == num) {
                // 匹配上了，直接return
                return true;
            } else {
                // 这里的index是二分的下标，当array[index]>num的时候才进来，说明右边的数据都
                // 小于num，所以需要直接舍弃下标index以上的数据，所以数组的长度应该是从index-1开始
                // 固这里的就是 maxIndex = index - 1
                maxIndex = index - 1;
            }
        }
        return false;
    }


    /**
     * 有序数组中找到<=num最右的位置
     *
     * @param array
     * @param num
     * @return
     */
    public static int findArrayRightData(int[] array, int num) {
        // 最大的位置
        int maxIndex = array.length - 1;
        // 二分的位置
        int branchIndex = 0;
        // 需要返回的值
        int returnIndex = 0;
        // 防止数组下标越界：二分的位置需要小于maxIndex
        while (branchIndex <= maxIndex) {
            // 下标
            int index = (branchIndex + maxIndex) / 2;
            if (array[index] <= num) {
                returnIndex = index;
                // 为什么要加一：是因为当array[index] 等于num的时候，需要加一，扩大向右二分的边界，
                // 方便找到最右的位置
                branchIndex = index + 1;
            } else if (array[index] > num) {
                // 条件是需要找打<=num最右的位置，所以这里下标index以上的数据都直接舍弃掉
                // 所以数组下标从index-1开始，再进行二分
                maxIndex = index - 1;
            }

        }
        return returnIndex;
    }

    /**
     * 有序数组中找到>=num最左的位置
     * 1 2 2 3 4 5
     *
     * @param array
     * @param num
     * @return
     */
    public static int findArrayLeftData(int[] array, int num) {
        // 得到array数组的下标
        int maxIndex = array.length - 1;
        // 记录二分的位置
        int branchIndex = 0;
        // 需要返回的值
        int returnIndex = 0;
        // 防止数组下标越界：二分的位置需要小于maxIndex
        while (branchIndex <= maxIndex) {
            // 二分的位置
            int index = (branchIndex + maxIndex) / 2;
            if (array[index] >= num) {
                /*
                    当array[index] >= num的时候，符合条件，记录下需要返回的值，然后我们需要向左缩小范围，所以需要把闭合区间的值给减一，所以就是
                    maxIndex = index -1
                 */
                returnIndex = index;
                maxIndex = index - 1;
            } else {
                // 题目是需要找到>=num 的，这里的进来的都是小于num，所以左边的不要了，下次的二分地址应该从index+1开始
                branchIndex = index + 1;
            }
        }
        return returnIndex;
    }


    public static void main(String[] args) {

        int[] array = {1, 9, 11, 4, 25, 6, 7, 33, 12, 5, 43, 3};
        // 选择排序：每次轮询查出最小的数
        DataSort.selectSort(array);
        DataSort.printlnArray(array);
        boolean arrayData = findArrayData(array, 13);
        int arrayRightData = findArrayRightData(array, 13);
        int arrayLeftData = findArrayLeftData(array, 13);

        System.out.println(arrayData);
        System.out.println("有序数组中找到<=num最右的位置下标：" + arrayRightData);
        System.out.println("有序数组中找到>=num最左的位置下标：" + arrayLeftData);


    }


}
